#include <bits/stdc++.h>
using namespace std;

/*
3272. 统计好整数的数目
已解答
困难
相关标签
相关企业
提示
给你两个 正 整数 n 和 k 。

如果一个整数 x 满足以下条件，那么它被称为 k 回文 整数 。

x 是一个 回文整数 。
x 能被 k 整除。
如果一个整数的数位重新排列后能得到一个 k 回文整数 ，那么我们称这个整数为 好 整数。比方说，k = 2 ，那么 2020 可以重新排列得到 2002 ，2002 是一个 k 回文串，所以 2020 是一个好整数。而 1010 无法重新排列数位得到一个 k 回文整数。

请你返回 n 个数位的整数中，有多少个 好 整数。

注意 ，任何整数在重新排列数位之前或者之后 都不能 有前导 0 。比方说 1010 不能重排列得到 101 。

 

示例 1：

输入：n = 3, k = 5

输出：27

解释：

部分好整数如下：

551 ，因为它可以重排列得到 515 。
525 ，因为它已经是一个 k 回文整数。
示例 2：

输入：n = 1, k = 4

输出：2

解释：

两个好整数分别是 4 和 8 。

示例 3：

输入：n = 5, k = 6

输出：2468

 

提示：

1 <= n <= 10
1 <= k <= 9
*/

// 法一
class Solution {
	public:
	using ll = long long;
	long long countGoodIntegers(int n, int k) {
		// 阶乘数组
		vector<ll> FAC(n + 1);
		FAC[0] = 1;
		for (int i = 1; i <= n; ++i) {
			FAC[i] = FAC[i - 1] * i;
		}

		// 存储数字组合
		unordered_set<string> seen;     
		// 回文数
		const int base = pow(10, (n - 1) / 2);  // 前半部分
		const int start = base;
		const int end = base * 10;;

		ll ans = 0;
		// 遍历回文前半部分
		for (int left = start; left < end; ++left) {
			// 奇偶有区别
			string leftStr = to_string(left);
			string rightStr(leftStr.rbegin(), leftStr.rend());
			if (n % 2 == 1)     rightStr = rightStr.substr(1);      // 奇数位时去除中间字符重复

			// 验证回文位数的有效性
			string paliStr = leftStr + rightStr;
			if (paliStr.size() != n)    continue;

			// 回文筛选
			const ll pali = stoll(paliStr);
			if (pali % k != 0) continue; // 跳过无法被k整除的回文

			// 唯一排列组合统计
			string chars = paliStr;
			sort(chars.begin(), chars.end());
			if (seen.count(chars)) continue; // 跳过已处理的组合
			seen.insert(chars);

			// 统计各数字出现频次
			vector<int> cnt(10, 0);     // 0-9的数字计数器
			for (char c : chars) {
				cnt[c - '0']++;
			}
			// 计算有效排列数（排除前导零情况）
			long long total = (n - cnt[0]) * FAC[n - 1]; // 首字母非零的排列基数
			// 应用重复元素的排列公式：n!/(n1!n2!...nk!)
			for (int i = 0; i < 10; ++i) {
				if (cnt[i] > 0) {
					total /= FAC[cnt[i]]; // 消除重复数字的影响
				}
			}
			ans += total;               // 累加到最终结果
		}
		return ans;
	}
};

// 法二
#define ll long long  
// 使用长整型防止计算溢出
class Solution {
public:
    
    long long countGoodIntegers(int n, int k) {
        unordered_set<string> st;   // 存储已处理的唯一数字组合
        int p[10] = {0};           // 数字出现次数计数器（0-9）
        ll z[11] = {0}, ans = 0;   // z: 阶乘缓存数组 | ans: 结果累加器
        z[0] = 1;                  // 初始化0! = 1

        // 预计算1!到n!提升排列计算效率[5,11](@ref)
        for(int i = 1; i <= n; i++) {
            z[i] = z[i-1] * i;
        }

        // 深度优先搜索生成回文数候选
        std::function<void(ll, ll, ll)> dfs = [&](ll l, ll r, ll temp) -> void {
            // 递归终止条件：左半部分处理完毕
            if(l < r) {
                // 剪枝：仅处理能被k整除的回文数
                if(temp % k != 0) return;

                // 标准化数字组合（排序去重）
                string s = to_string(temp);
                sort(s.begin(), s.end());

                // 检查是否已处理过相同数字组合[3,6](@ref)
                if(st.find(s) == st.end()) {
                    st.insert(s);

                    // 统计各数字出现次数
                    for(int i = 0; i < s.size(); i++) {
                        p[s[i]-'0']++;
                    }

                    // 计算有效排列数（排除前导零）
                    ll dif = 1;
                    // 计算非零数字的重复排列因子[5,11](@ref)
                    for(int i = 1; i < 10; i++) {
                        dif *= z[p[i]];
                        p[i] = 0;
                    }

                    // 处理含零的特殊情况
                    if(p[0] != 0) {
                        // 总排列数 - 前导零排列数[3,6](@ref)
                        ans += z[n]/(dif * z[p[0]]) - z[n-1]/(dif * z[p[0]-1]);
                        p[0] = 0;
                    } else {
                        ans += z[n]/dif;
                    }
                }
                return;
            }

            // 递归生成回文数的左右部分
            ll i = (r == 1) ? 1 : 0;  // 最高位不能为零[3,7](@ref)
            for(; i < 10; i++) {
                // 动态构建回文数（左半部分递减，右半部分递增）
                if(l != r) {
                    dfs(l / 10, r * 10, l * i + r * i + temp);  // 处理中间对称位
                } else {
                    dfs(l / 10, r * 10, l * i + temp);          // 处理中心对称位
                }
            }
        };

        // 启动DFS：初始左半部分为10^(n-1)，右半部分初始为1
        dfs(pow(10, n-1), 1, 0);
        return ans;
    }
};